package 牛客;

import java.util.Scanner;

class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(char val) {
        this.val = val;
    }
}
public class pKY11二叉树遍历 {

    public static int i=0;
    //因为字符串是前序遍历的结果，因此构建树也要以前序的方式构建
    public static TreeNode creatTree(String s) {
        if (s==null) return null;

        TreeNode root=null;
        if (s.charAt(i)!='#') {
            root=new TreeNode(s.charAt(i));
            i++;
            root.left=creatTree(s);
            root.right=creatTree(s);
        }else {
            i++;
        }
        return root;
    }

    public static void inOrder(TreeNode root) {
        if (root==null) return;

        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        TreeNode root = creatTree(s);//构造二叉树

        inOrder(root);//对二叉树进行中序遍历
    }

}
